package leetcode.day_2021_05_25_2021_05_31;

/**
 * 97. 交错字符串
 * https://leetcode-cn.com/problems/interleaving-string/
 */
public class LeetCode0097 {
    public static void main(String[] args) {
        System.out.println(isInterleave("",
                "b",
                "b"));
    }

    public static boolean isInterleave(String s1, String s2, String s3) {
        char[] s1Arr = s1.toCharArray();
        char[] s2Arr = s2.toCharArray();
        char[] s3Arr = s3.toCharArray();
        if(s1Arr.length + s2Arr.length != s3Arr.length) {
            return false;
        }
        int m = s1.length(), n = s2.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for(int i=1; i<=m; i++) {
            if(s1Arr[i-1] == s3Arr[i-1]) {
                dp[i][0] = true;
            }
        }
        for(int j=1; j<=n; j++) {
            if(s2Arr[j-1] == s3Arr[j-1]) {
                dp[0][j] = true;
            }
        }

        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                dp[i][j] = (dp[i-1][j] && s1Arr[i-1] == s3Arr[i+j-1]) ||
                        (dp[i][j-1] && s2Arr[j-1] == s3Arr[i+j-1]);
            }
        }
        return dp[m][n];
    }
}
